package algorithm.leetcode;

import java.util.Deque;
import java.util.LinkedList;

public class LeetCode_993_isCousins {
    public boolean isCousins(TreeNode root, int x, int y) {
        Deque<TreeNode[]> q = new LinkedList<>();
        q.offer(new TreeNode[]{root, null});
        while (!q.isEmpty()) {
            int size = q.size();
            int fx = 0, fy = 0;
            TreeNode[] candidates = new TreeNode[2];
            for (int i = 0; i < size; i++) {
                TreeNode[] poll = q.poll();
                TreeNode cur = poll[0], parent = poll[1];
                if (cur.val == x) {
                    fx = 1;
                    candidates[0] = parent;
                } else if (cur.val == y) {
                    fy = 1;
                    candidates[1] = parent;
                }
                if (cur.left != null) q.offer(new TreeNode[]{cur.left, cur});
                if (cur.right != null) q.offer(new TreeNode[]{cur.right, cur});
            }
            if ((fx | fy) == 0) continue;
            if ((fx ^ fy) == 1) return false;
            if ((fx & fy) == 1) return candidates[0] != candidates[1];
        }
        return false;
    }

}
